浙江大学2017-18秋冬《数据结构基础》期中模拟练习
开始时间1/1/2016, 12:00:00 AM
结束时间1/18/2038, 12:00:00 AM
答题时长45分钟
考生-
得分87
总分100

判断题总分:15得分:12
1-1

In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order. (3分)

       

评测结果:答案正确(3 分)
1-2

In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. (3分)

       

评测结果:答案正确(3 分)
1-3

If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (3分)

       

评测结果:答案正确(3 分)
1-4

For a sequentially stored linear list of length NN, the time complexities for deleting the first element and inserting the last element are O(1)O(1) and O(N)O(N), respectively. (3分)

       

评测结果:答案错误(0 分)
1-5

N2logNN^2 logN and NlogN2N logN^2 have the same speed of growth. (3分)

       

评测结果:答案正确(3 分)
单选题总分:65得分:55
2-1

The recurrent equations for the time complexities of programs P1 and P2 are:

  • P1: T(1)=1T(1)=1, T(N)=T(N/2)+1T(N)=T(N/2)+1;
  • P2: T(1)=1T(1)=1, T(N)=2T(N/2)+1T(N)=2T(N/2)+1;

Then the correct conclusion about their time complexities is: (5分)

评测结果:答案错误(0 分)
2-2

The result of performing three DeleteMin operations in the min-heap {1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} is: (5分)

评测结果:答案正确(5 分)
2-3

Given a directed graph G=(V, E) where V = {v1, v2, v3, v4, v5, v6} and E = {<v1,v2>, <v1,v4>, <v2,v6>, <v3,v1>, <v3,v4>, <v4,v5>, <v5,v2>, <v5,v6>}. Then the topological order of G is: (5分)

评测结果:答案正确(5 分)
2-4

Which of the following statements is TRUE about topological sorting? (5分)

评测结果:答案正确(5 分)
2-5

To delete p from a doubly linked list, we must do: (6分)

评测结果:答案正确(6 分)
2-6

In-order traversal of a binary tree can be done iteratively. Given the stack operation sequence as the following:

push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()

Which one of the following statements is TRUE? (6分)

评测结果:答案正确(6 分)
2-7

Given a quadtree(四叉树) with 2 nodes of degree 2, 3 nodes of degree 3, 4 nodes of degree 4. The number of leaf nodes in this tree is __. (5分)

评测结果:答案错误(0 分)
2-8

The array representation of a disjoint set is given by { 4, 6, 5, 2, -3, -4, 3 }. If the elements are numbered from 1 to 7, the resulting array after invoking Union(Find(7),Find(1)) with union-by-size and path-compression is: (5分)

评测结果:答案正确(5 分)
2-9

If an undirected graph G = (V, E) contains 7 vertices. Then to guarantee that G is connected in any cases, there has to be at least __ edges. (6分)

评测结果:答案正确(6 分)
2-10

Insert { 5, 11, 13, 1, 3, 6 } one by one into an initially empty binary search tree. The post-order traversal sequence of the resulting tree is: (6分)

评测结果:答案正确(6 分)
2-11

Suppose that an array of size m is used to store a circular queue. If the head pointer front and the current size variable size are used to represent the range of the queue instead of front and rear, then the maximum capacity of this queue can be: (5分)

评测结果:答案正确(5 分)
2-12

How many leaf node does a complete binary tree with 2435 nodes have? (6分)

评测结果:答案正确(6 分)
程序填空题总分:20得分:20
5-1

The function is to find the K-th smallest element in a list A of N elements. The function BuildMaxHeap(H, K) is to arrange elements H[1] ... H[K] into a max-heap. Please complete the following program.

ElementType FindKthSmallest ( int A[], int N, int K )
{   /* it is assumed that K<=N */
    ElementType *H;
    int i, next, child;

    H = (ElementType *)malloc((K+1)*sizeof(ElementType));
    for ( i=1; i<=K; i++ ) H[i] = A[i-1];
    BuildMaxHeap(H, K);

    for ( next=K; next<N; next++ ) {
        H[0] = A[next];
        if ( H[0] < H[1] ) {
            for ( i=1; i*2<=K; i=child ) {
                child = i*2;
                if ( child!=K && (5分) ) child++;
                if ( (5分) )
                    H[i] = H[child];
                else break;
            }
            H[i] = H[0];
        }
    }
    return H[1];
}

评测结果:答案正确(10 分)
序号结果得分
0答案正确5
1答案正确5
5-2

Please fill in the blanks in the program which performs Find as a Union/Find operation with path compression.

SetType Find ( ElementType X, DisjSet S )
{   
   ElementType root, trail, lead;

   for ( root = X; S[root] > 0; (5分) ) ;  
   for ( trail = X; trail != root; trail = lead ) {
      lead = S[trail] ;   
      (5分);   
   } 
   return root;
}
评测结果:答案正确(10 分)
序号结果得分
0答案正确5
1答案正确5